package primary.code12_dp;

import lombok.extern.slf4j.Slf4j;

/**
 * 问题：
 * Bob被困在  m * n 的矩阵范围内
 * 初始位置为(a,b)， Bob 只能上下左右移动，如果碰到边界则死亡
 * Bob 移动K步，计算一共有多少存活线路？
 */
@Slf4j
public class Code05_BobSurvive {
    public static int survice1(int m, int n, int a, int b, int k) {
        if (a < 0 || b < 0 || a > m || b > n) {
            return 0;
        }
        if (k == 0) {
            return 1;
        }
        return survice1(m, n, a + 1, b, k - 1) +
                survice1(m, n, a - 1, b, k - 1) +
                survice1(m, n, a, b + 1, k - 1) +
                survice1(m, n, a, b - 1, k - 1);
    }

    public static int survice2(int m, int n, int a, int b, int k) {
        int[][][] dp = new int[m + 1][n + 1][k + 1];
        for (int x = 0; x < m + 1; x++) {
            for (int y = 0; y < n + 1; y++) {
                dp[x][y][0] = 1;
            }
        }
        for (int z = 1; z < k + 1; z++) {
            for (int x = 0; x < m + 1; x++) {
                for (int y = 0; y < n + 1; y++) {
                    dp[x][y][z] =
                            getVal(dp, x + 1, y, z - 1) +
                            getVal(dp, x - 1, y, z - 1) +
                            getVal(dp, x, y + 1, z - 1) +
                            getVal(dp, x, y - 1, z - 1);
                }
            }
        }
        return dp[a][b][k];
    }

    private static int getVal(int[][][] dp, int row, int col, int h) {
        if (row < 0 || row >= dp.length) {
            return 0;
        }
        if (col < 0 || col >= dp[0].length) {
            return 0;
        }
        return dp[row][col][h];
    }

    public static void main(String[] args) {
        long start1 = System.currentTimeMillis();
        int res1 = survice1(10, 10, 4, 4, 15);
        long time1 = System.currentTimeMillis() - start1;
        log.info("暴力递归计算，结果：{}，耗时：{}", res1, time1); // 暴力递归计算，结果：903593692，耗时：1409

        long start2 = System.currentTimeMillis();
        int res2 = survice2(10, 10, 4, 4, 15);
        long time2 = System.currentTimeMillis() - start2;
        log.info("DP计算，结果：{}，耗时：{}", res2, time2); // DP计算，结果：903593692，耗时：0
    }
}
